package org.example.everyday;

public class Lc798 {

    public static void main(String[] args) {
        Lc798 lc798 = new Lc798();
        int[] nums = {2, 3, 1, 4, 0};
        int result = lc798.bestRotation(nums);
        System.out.println(result);

    }

    public int bestRotation(int[] nums) {
        int[] diff = getDiff(nums);

        int ans = 0, max = diff[0];
        for(int i = 1 ; i < nums.length ; i++) {
            diff[i] += diff[i - 1];
            if(diff[i] > max) {
                max = diff[i];
                ans = i;
            }
        }
        return ans;
    }

    private int[] getDiff(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];

        for(int i = 0 ; i < len ; i++) {


            if(nums[i] <= i){
                ans[0]++;
                ans[(i+1-nums[i]) % len]--;
                ans[(i+1) % len]++;
            }else{
                ans[(i+1) % len]++;
                ans[(i+1+len-nums[i]) % len]--;
            }
        }

        return ans;
    }
}
